package zhengqc.sort.quick_sort;
import zhengqc.common.Pair;
import zhengqc.sort.Sort;

import java.util.Random;

public class ThreeWayQuickSort<E extends Comparable<E>> extends Sort<E> {
    private Random random;
    public ThreeWayQuickSort() {
        this.sortName = "ThreeWayQuickSort";
        this.random = new Random();
    }
    @Override
    public void sort(E[] array) {
        sort(array, 0, array.length-1);
    }
    private void sort(E[] array, int left, int right) {
        if (left >= right) return;
        Pair<Integer, Integer> pair = partition(array, left, right);
        sort(array, left, pair.first);
        sort(array, pair.second, right);
    }
    private Pair<Integer, Integer> partition(E[] array, int left, int right) {
        // 生成 [left, right] 之间的随机索引
        int p = left + random.nextInt(right-left+1);
        swap(array, left, p);

        // 循环不变量 array[left+1...lt] < v, array[lt+1...i-1] == v, array[gt...right] > v
        int lt = left, i = left + 1, gt = right +1;
        while (i < gt) {
            if (array[i].compareTo(array[left]) < 0) {
                ++lt;
                swap(array, lt, i);
                ++i;
            } else if (array[i].compareTo(array[left]) > 0) {
                --gt;
                swap(array, gt, i);
            } else { // array[i] == array[left]
                ++i;
            }
        }
        swap(array, left, lt);
        return new Pair<>(lt-1, gt);
    }
    private static <E> void swap(E[] array, int i, int j) {
        E t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
